# -*- coding: utf-8 -*-
# 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表
# 示例:
# 给定 1->2->3->4, 你应该返回 2->1->4->3
# 说明:
# 你的算法只能使用常数的额外空间。
# 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

def printList(head):
    current = head;
    v_log = [];
    while current:
        v_log.append(current.val);
        current = current.next;
    print v_log;

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

# # 使用3个定位的指针
# class Solution(object):
#     def swapPairs(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head:
#             return None;
#         hhead = ListNode(-1);
#         hhead.next = head;
#         current = hhead;
#         after = head;
#         pre = head.next;
#         while after and pre:
#             after.next = pre.next;
#             pre.next = after;
#             current.next = pre;

#             current = after;
#             after = after.next;
#             if after:
#                 pre = after.next;
#         return hhead.next;

# # 使用1个定位的指针
# class Solution(object):
#     def swapPairs(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head:
#             return None;
#         hhead = ListNode(-1);
#         hhead.next = head;
#         current = hhead;
#         while current.next and current.next.next:
#             temp = current.next;
#             current.next = current.next.next;
#             temp.next = current.next.next;
#             current.next.next = temp;
#             current = temp;
#         return hhead.next;

# 最快的算法 使用python的赋值特性
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre, pre.next = self, head;
        while pre.next and pre.next.next:
            a = pre.next;
            b = a.next;
            pre.next, b.next, a.next = b, a, b.next;
            pre = a;
        return self.next;

l = ListNode(2);
l.next = ListNode(1);
l.next.next = ListNode(4);
l.next.next.next = ListNode(3);
t = Solution();
printList(t.swapPairs(l));
